<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            最后一块石头的重量 II：
            输入：stones = [2,7,4,1,8,1]
            输出：1
            解释：
            组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
            组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
            组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
            组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

            题目描述：
            1. 从里面任意取2个石头，如果重量相同，就一起粉碎
            2. 如果重量不同，x != y, x会完全被粉碎，y的重量 => y - x
            3. 再循环
            4. 最后剩下一个石头，返回的石头最小可能重量

            判断是01背包：
            这道题目的关键是如何把“两两取石头”转化为“取石头到背包里面”最大价值问题
            0. 两两取石头出来相撞，其实最终取出来就是两组石头，比如[2,7,4,1,8,1]里面 [2, 1, 7]两组[1, 4, 8] 2是要和1相撞 1是要和4相撞
               这两组石头重量各自都无限接近重量总和的一半，要很大才能接近，各自相撞的石头才会最小；所以接近的那个一半就是我们要求的背包最大容量
            1. 每个石头只能取1次，是01背包
            3. 重量和价值都是石头的数值


            五部曲：
            1. dp[j]的含义：j是石头的重量，dp[j]是拿到石头最大重量，也是最大价值和
            2. 确定递推公式：dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]) 注意，nums[i]不仅是重量，也是价值
            3. 初始化dp数组，如果遍历的数字都是正整数，可以都初始化为0，否则要初始化负无穷？为什么
            4. 确定遍历顺序，和01背包一样，先遍历石头，再遍历背包的容量；遍历背包的容量时要倒序遍历
            5. 递推一下：[2,7,4,1,8,1]这个，就要初始化为长度为11的数组

        */
        var lastStoneWeightII = function(nums) {
            let sum = 0
            nums.forEach(item => sum += item)
            let len = Math.floor(sum / 2)
            // 初始化
            let dp = new Array(len + 1).fill(0) // 数组就是从0-11的数
            for (let i = 0; i < nums.length; i++) {
                for (let j = len; j >= nums[i]; j--) {
                    if (i === 2) {
                        console.log(dp, 'dp');
                        debugger
                    }
                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]) 
                }
            }
            return sum - dp[len] - dp[len]
        };
        console.log(lastStoneWeightII([2,7,4,1,8,1]));
        console.log(lastStoneWeightII([31,26,33,21,40]));
    </script>
</body>

</html>